# 110. 平衡二叉树
# 给定一个二叉树，判断它是否是高度平衡的二叉树。
# 本题中，一棵高度平衡二叉树定义为：
# 一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。
#
#
# 示例 1：
# 输入：root = [3,9,20,null,null,15,7]
# 输出：true
#
# 示例 2：
# 输入：root = [1,2,2,3,3,null,null,4,4]
# 输出：false
#
# 示例 3：
# 输入：root = []
# 输出：true
# 求高度用后序遍历
# 求深度用前序遍历

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def isBalanced(self, root) -> bool:
        # 1.明确递归函数参数和返回值，
        def gethegith(root):
            # 2.明确终止条件
            if not root:
                return 0
            # 3.单次递归逻辑
            left_h = gethegith(root.left)
            if left_h == -1:
                return -1
            right_h = gethegith(root.right)
            if right_h == -1:
                return -1
            if abs(left_h - right_h) > 1:
                return -1
            return 1+ max(left_h,right_h)
        res = gethegith(root)
        if res == -1:
            return False
        else:
            return True

if __name__ == '__main__':
    # a41 = TreeNode(4)
    # a42 = TreeNode(4)
    # a31 = TreeNode(3,a41,a42)
    # a32 = TreeNode(3)
    # a21 = TreeNode(2,a31,a32)
    # a22 = TreeNode(2)
    # a11 = TreeNode(1,a21,a22)
    a31 = TreeNode(15)
    a32 = TreeNode(7)
    a22 = TreeNode(20,a31,a32)
    a21 = TreeNode(9)
    a11 = TreeNode(3,a21,a22)
    tmp = Solution()
    res = tmp.isBalanced(a11)
    print(res)

